package main.Q1301_1400;

import java.util.Stack;

public class Q1311_1320 {
    public static void main(String[] args) {
        System.out.println("Question1311：");
        System.out.println("Question1312：");
        System.out.println("Question1313：");
        System.out.println("Question1314：矩阵区域和");
        System.out.println("Question1315：祖父节点值为偶数的节点和");
        System.out.println("Question1316：");
        System.out.println("Question1317：");
        System.out.println("Question1318：");
        System.out.println("Question1319：连通网络的操作次数");
        System.out.println("Question1320：");
    }
}

class Question1314 {
    public int process(int[][] mat, int r, int c, int k) {
        int sum = 0, row = mat.length, col = mat[0].length;
        for (int i = r - k; i <= r + k && i < row; i++) {
            for (int j = c - k; j <= c + k && j < col; j++) {
                if (i >= 0 && j >= 0) sum += mat[i][j];
            }
        }
        return sum;
    }

    public int[][] matrixBlockSum(int[][] mat, int k) {
        int row = mat.length, col = mat[0].length;
        int[][] answer = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                answer[i][j] = process(mat, i, j, k);
            }
        }
        return answer;
    }
}

class Question1315 {
    int result = 0;

    public void process(TreeNode root, int father, int grandfather) {
        if (grandfather % 2 == 0) {
            result += root.val;
        }
        if (root.left != null) {
            process(root.left, root.val, father);
        }
        if (root.right != null) {
            process(root.right, root.val, father);
        }
    }

    public int sumEvenGrandparent(TreeNode root) {
        process(root,-1,-1);
        return result;
    }
}

class Question1319 {
    class UnionFind {
        private int[] father;//记录元素上层元素
        private int[] size;//记录当前元素所在集合的元素个数
        private int breachCount;//当前并查集中集合个数

        public UnionFind(int n) {//初始化，上层元素为自身
            this.breachCount = n;
            father = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
                size[i] = 1;
            }
        }

        public int findTop(int x) {
            Stack<Integer> path = new Stack<>();
            while (x != father[x]) {
                path.push(x);
                x = father[x];
            }
            while (!path.isEmpty()) father[path.pop()] = x;//压缩路径
            return x;
        }

        public void union(int x, int y) {//合并两集合
            int topX = findTop(x), topY = findTop(y);
            if (topX != topY) {//顶层元素大的集合并入顶层元素小的集合
                if (topX < topY) {
                    father[topY] = topX;
                    size[topX] = size[topX] + size[topY];
                } else {
                    father[topX] = topY;
                    size[topY] = size[topX] + size[topY];
                }
                breachCount--;
            }
        }

        public boolean isSameGather(int x, int y) {//判断两元素是否为同一集合
            if (findTop(x) == findTop(y)) return true;
            else return false;
        }

        public int getBreachCount() {//当前并查集中集合个数
            return this.breachCount;
        }
    }

    public int makeConnected(int n, int[][] connections) {
        UnionFind unionFind = new UnionFind(n);
        int surplusLineCount = 0;
        for (int[] con : connections) {
            if (unionFind.isSameGather(con[0], con[1])) {
                surplusLineCount++;
            } else {
                unionFind.union(con[0], con[1]);
            }
        }
        int result = -1, gatherCount = unionFind.getBreachCount();
        if (gatherCount == 1) result = 0;//一个集合
        else if (surplusLineCount >= gatherCount - 1) result = gatherCount - 1;
        return result;
    }
}